Triangle

Time: O(MxN); Space: O(N); medium

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Example 1:

Input: triangle =

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

Output: 11

Explanation:

  • The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Example 3:

Input: triangle =

[
     [2],
    [3,2],
   [6,5,7],
  [4,4,8,1]
]

Output: 12

Explanation:

  • The minimum path sum from top to bottom is 12 (i.e., 2 + 2 + 7 + 1 = 12).

Note:

  • Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

[1]:

from functools import reduce

class Solution1(object):
    """
    Time: O(M*N)
    Space: O(N)
    """
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if not triangle:
            return 0

        cur = triangle[0] + [float("inf")]

        for i in range(1, len(triangle)):
            next = []
            next.append(triangle[i][0] + cur[0])

            for j in range(1, i + 1):
                next.append(triangle[i][j] + min(cur[j - 1], cur[j]))

            cur = next + [float("inf")]

        return reduce(min, cur)

[2]:

s = Solution1()

triangle = [
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
assert s.minimumTotal(triangle) == 11

triangle = [
     [2],
    [3,2],
   [6,5,7],
  [4,4,8,1]
]
assert s.minimumTotal(triangle) == 12